NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/696

Text File | 1996-08-06 | 4KB | 124 lines

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Thu, 04 Apr 96 18:57:54 GMT
Organization: none
Message-ID: <[e-mail]>
References: <4iokop$[e-mail]> <4iqjar$[e-mail]> <4jgltp$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4jgltp$[e-mail]>
           [e-mail] "James Bonfield" writes:

>I now agree that non antisymmetric or nontransitive sort comparison functions
>are indeed invalid. I can see how this can be construed from the ansi
>standard, but can also see how it's possible to construe otherwise.

I don't. 7.10.5.2:

"The contents of the array are sorted into ascending
 order according to a comparison function pointed to by compar".

If the comparison function produces inconsistent results then it is at odds
with that sentence. At best that sentence has no well-defined meaning and
the 'sort' operation as a whole has undefined behaviour.

>it doesn't really state such things explicitly. Anyway, that aside I thought I
>should reply to the last note about this.
>
>In article <4iqjar$[e-mail]> [e-mail] (Norman Diamond)
> writes:
>
>>>such functions appear to make [one implementation's] qsort() function
>>>underflow the passed array.
>>
>>This should not happen.
>
>Well, that depends on whether or not you class qsorts behaviour as undefined
>for such functions.

To put it another way, if there is a defined behaviour with such a function,
what is it?

>>>#define NUM_ELE 10
>>>int main() {
>>>    int i;
>>>    int crashme;     /* removing this line fixes things! */
>>
>>This makes me suspicious that your test program is not exactly what you
>>posted, and your test program has a bug in some other part of its code
>>that already yielded undefined behavior.
>
>Actually it's true - it does cause it to go wrong. I've got an example now
>that used explicitly defined numbers to cause a crash. With the crashme line
>in the program dies. Without it the program modifies memory not within the
>boundaries of qsort. My program is:
>
>#include <stdio.h>
>#include <stdlib.h>
>
>static int sort_func(const void *pa, const void *pb)
>{
>    const int *a = (int *)pa;
>    const int *b = (int *)pb;

It would be more consistent (as well as killing a warning from my compiler)
if you cast to (const int *), better still don't cast at all.

>
>    return *a > *b;
>}

This clearly violates a 'shall' in the standard and results in undefined
behaviour. With the specific data in this case return *a - *b; would be OK.

"The function shall return an integer less than, equal to, or greater than
 zero if the first argument is considered to be respectively less than, equal
 to, or greater than the second."

>#define NUM_ELE 10
>int main() {
>    int i;
>    int crashme;     /* removing this line fixes things! */
>    int sortme[NUM_ELE] = {148, 104, 126, 74, 108, 131, 129, 131, 125, 77};
>
>    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
>    putchar('\n');
>
>    qsort((void *)(sortme+1), NUM_ELE-2, sizeof(int), sort_func);
>
>    for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
>    putchar('\n');
>
>    return 0;
>}
>
>>b < c and c < a).  As for whether qsort() is required to contend with
>>such nonsense, it "probably" isn't.
>
>Agreed. Hence the above discoveries are most likely entirely within the realm
>of acceptability.
>
>Perhaps the most interesting point to come out of this is the inefficiency of
>some qsort algorithms. Sorting 100,000 elements (with a "consistent" sort
>comparison function) gave the following approximations (ran several times with
>random input - of course these results may just reflect the random number
>generator woes!):
>
>OSF/1 V3.0      ~72K
>Linux (gnu lib) ~153K
>Irix 5.3        ~170K
>Solaris 5.3     ~305K

What do these numbers represent?

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------